#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> ans(n, vector<int>(n, 0));
        int mvx[4] = {1, 0, -1, 0};
        int mvy[4] = {0, 1, 0, -1};
        
        int cnt = 0; int idx = 0;
        int x, y; x=-1; y=0;
        for(int i=0; i<n; ++i){
            for(int j=0; j<n; ++j){
                int newx = x+mvx[cnt%4];
                int newy = y+mvy[cnt%4];
                if(newx<0 || newy<0 || newx>=n || newy>=n || ans[newy][newx]!=0){
                    ++cnt;
                    --j;
                    continue;
                }
                ans[newy][newx] = ++idx;
                x = newx; y = newy;
            }
        }
        return ans;
    }
};

int main(){

}